package com.tom.architect02.structure.chart3;

import android.util.Log;

import java.util.ArrayDeque;

/**
 * Created by hcDarren on 2018/11/11.
 */

public class Graph {
    public final static int MAX_WEIGHT = 65536;
    // 顶点的个数
    int vertexSize;
    // 顶点的集合
    int[] vertexes;
    // 边的集合
    int[][] matrix;

    public Graph(int vertexSize, int[] vertexes, int[][] matrix) {
        this.vertexSize = vertexSize;
        this.vertexes = vertexes;
        this.matrix = matrix;
    }

    public void breadthFirstSearch() {
        // 访问过的顶点角标
        boolean[] visited = new boolean[vertexSize];

        // 把第一个顶点加入
        ArrayDeque<Integer> vertexQ = new ArrayDeque<>();
        vertexQ.push(vertexes[3]);

        while (!vertexQ.isEmpty()) {
            // 当前顶点，但是我们这里又是角标
            int currentVertex = vertexQ.removeFirst();
            // 查询当前角标
            int index = currentVertex;
            if (!visited[index]) { // O(1)
                Log.e("TAG", "访问到了顶点：" + currentVertex);
                visited[index] = true;

                for (int i = 0; i < vertexSize; i++) {
                    if (matrix[index][i] == 1 && !visited[i]) {// 代表与 index 相连
                        // 还可以写一个判断，如果队列中不包含 再往里面新增 , 画蛇添足
                        // if(!vertexQ.contains(vertexes[i])) {  // 0(N)
                        vertexQ.addLast(vertexes[i]);
                        // }
                    }
                }
            }
        }
    }


    public void prim() {
        // 定义一个数组内存，当前修好村庄 , lowcost = 0 代表已经修了
        int[] lowcost = new int[vertexSize];

        // 第一列的数据先放到 lowcost
        for (int i = 0; i < vertexSize; i++) {
            lowcost[i] = matrix[0][i];
        }

        int sum = 0;

        for (int i = 1; i < vertexSize; i++) {
            int min = MAX_WEIGHT;
            int minId = 0;

            // 找最小的 ，之间是否联通
            for (int j = 1; j < vertexSize; j++) {
                if (lowcost[j] < min && lowcost[j] != 0) {
                    min = lowcost[j];
                    minId = j;
                }
            }

            Log.e("TAG", "找到村庄：" + vertexes[minId] + " , 修路距离：" + min);
            lowcost[minId] = 0;
            sum += min;

            // 这个代码有问题
            for (int k = 0; k < vertexSize; k++) {
                // 边考虑边淘汰
                if (matrix[minId][k] < lowcost[k] && lowcost[k] > 0) {
                    lowcost[k] = matrix[minId][k];
                }
            }

            /*for (int number : lowcost) {
                Log.e("TAG","number = "+number);
            }
            Log.e("TAG","==================================== ");*/
        }

        Log.e("TAG", "最短的路径是：" + sum);
    }

    // 迪杰斯特拉算法
    public void dijstra() {
        // 最短路径 ， 有没有找到最短距离
        // 有没找到最短路径
        boolean[] isPath = new boolean[vertexSize];
        // 存放每个村庄的最短路径
        int[] shortPath = new int[vertexSize];

        // 1. 第一列的数据先放到 shortPath
        for (int i = 0; i < vertexSize; i++) {
            shortPath[i] = matrix[0][i];
        }
        // 2. 到自己的距离
        shortPath[0] = 0;
        isPath[0] = true;
        int minId = 0; // 最短的角标

        // 3. 外层循环，遍历所有村庄
        for (int i = 1; i < vertexSize; i++) { // 每个村庄都要找
            int min = MAX_WEIGHT;
            for (int j = 1; j < vertexSize; j++) { // 找最小的
                // 当前有没有被找到， 且小于min
                if (!isPath[j] && shortPath[j] < min) {
                    minId = j;
                    min = shortPath[j]; // 找到最短的
                }
            }
            isPath[minId] = true; // 已经找到

            // 4. 更新最短路径，更新
            for (int j = 0; j < vertexSize; j++) {
                // 没找到最近的；
                // (min + matrix[minId][j]) < shortPath[j]  之前的最小值+当前节点权值 < 之前保存的最短值。
                if (!isPath[j] && (min + matrix[minId][j]) < shortPath[j]) {
                    shortPath[j] = min + matrix[minId][j]; // 替换
                }
            }

            for (int k = 0; k < vertexSize; k++) {
                Log.e("TAG", shortPath[k]+" "); // 打印遍历过程中的最短距离
            }
            Log.e("TAG", "===================");
        } // for循环，不断地找。

        for (int i = 0; i < vertexSize; i++) {
            Log.e("TAG", "顶点 0 到顶点 " + i + " 的最短距离为：" + shortPath[i]);
        }
    }
    // 顶点0到其他点的最短距离

}
